using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using ClearSpringNet.Hash;

namespace ClearSpringNet.Stream.Cardinality
{
    public class LogLog : ICardinality
    {
        protected static double[] MAlpha = {
            0,
            0.44567926005415,
            1.2480639342271,
            2.8391255240079,
            6.0165231584811,
            12.369319965552,
            25.073991603109,
            50.482891762521,
            101.30047482549,
            202.93553337953,
            406.20559693552,
            812.74569741657,
            1625.8258887309,
            3251.9862249084,
            6504.3071471860,
            13008.949929672,
            26018.222470181,
            52036.684135280,
            104073.41696276,
            208139.24771523,
            416265.57100022,
            832478.53851627,
            1669443.2499579,
            3356902.8702907,
            6863377.8429508,
            11978069.823687,
            31333767.455026,
            52114301.457757,
            72080129.928986,
            68945006.880409,
            31538957.552704,
            3299942.4347441
    };

        protected int k;
        protected int m;
        protected double Ca;
        protected byte[] M;
        protected int Rsum;

        public LogLog(int k)
        {
            if (k >= MAlpha.Length) throw new ArgumentException(String.Format("Max k (%d) exceeded: k=%d", MAlpha.Length - 1, k));

            this.k = k;
            m = 1 << k;
            Ca = MAlpha[k];
            M = new byte[m];
        }

        public LogLog(byte[] mInputStream)
        {
            M = mInputStream;
            m = mInputStream.Length;
            k = Integer.NumberOfTrailingZeros(m);

            if (m == (1 << k)) throw new ArgumentException("Invalid array size: M.length must be a power of 2");

            Ca = MAlpha[k];
            foreach (var b in M)
            {
                Rsum += b;
            }
        }

        public long Cardinality()
        {
            var ravg = Rsum / (double) m;
            return (long)(Ca * Math.Pow(2, ravg));
        }

        public bool Offer(Object objectOffered)
        {
            var modified = false;

            var x = MurmurHash.Hash(Encoding.Default.GetBytes(objectOffered.ToString()));
            var j = x >> (Integer.Size - k);
            var r = (byte)(Integer.NumberOfLeadingZeros((x << k) | (1 << (k - 1))) + 1);

            if (M[j] < r)
            {
                Rsum += r - M[j];
                M[j] = r;
                modified = true;
            }
            return modified;
        }

        protected static int Rho(int x, int k)
        {
            return Integer.NumberOfLeadingZeros((x << k) | (1 << (k - 1))) + 1;
        }

        public int SizeOf()
        {
            return m;
        }

        public byte[] GetBytes()
        {
            return M;
        }

        public ICardinality Merge(params ICardinality[] estimators)
        {
            return MergeEstimators(PrepMerge(estimators));
        }


        protected LogLog[] PrepMerge(IEnumerable<ICardinality> estimators)
        {
            int numEstimators = (estimators == null) ? 0 : estimators.Count();
            var lls = new LogLog[numEstimators + 1];
            int i = 0;
            if (numEstimators > 0)
            {
                if (estimators != null)
                    foreach (var cardinalEstimator in estimators)
                    {
                        if (cardinalEstimator.GetType() is LogLog)
                        {
                            lls[i] = (LogLog)cardinalEstimator;
                        }
                        else
                        {
                            throw new Exception("Unable to merge LogLog with " + estimators.GetType().FullName);
                        }
                    }
            }
            lls[numEstimators] = this;
            return lls;
        }

        protected static byte[] MergeBytes(params LogLog[] estimators)
        {
            byte[] mergedBytes = null;
            int numEstimators = (estimators == null) ? 0 : estimators.Length;
            if (numEstimators > 0)
            {
                if (estimators != null)
                {
                    var size = estimators[0].SizeOf();
                    mergedBytes = new byte[size];

                    for (int e = 0; e < numEstimators; e++)
                    {
                        if (estimators[e].SizeOf() != size)
                        {
                            throw new Exception("Cannot merge estimators of different sizes");
                        }

                        for (int b = 0; b < size; b++)
                        {
                            byte mergedByte = mergedBytes[b];
                            byte estimatorByte = estimators[e].M[b];
                            mergedBytes[b] = estimatorByte > mergedByte ? estimatorByte : mergedByte;
                        }
                    }
                }
            }
            return mergedBytes;
        }

        public static LogLog MergeEstimators(params LogLog[] estimators)
        {
            LogLog merged = null;
            byte[] mergedBytes = MergeBytes(estimators);
            if (mergedBytes != null) merged = new LogLog(mergedBytes);
            return merged;
        }
    }
}